#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

#define APP_ORDER 1
#define ORG_ORDER 0
typedef struct ITEM Item;
typedef struct NODE Node;
typedef struct STACK Stack;

struct ITEM {
	unsigned addr;
	int	 data;
	int next;		// cause -1 for NULL
};

struct NODE {
	Item item;
	Node * next_org_order;
	Node * next_app_order;
};

struct STACK{
	Item item;
	Stack *next;
};

void addNode(Node*,Item);
Node * initList();
void destroyList(Node*);
void prtList(Node *,int);
Node * findNode(Node*,unsigned);
void addNode_(Node*,Node*);
Stack * initStack();
void push(Stack*,Item);
_Bool pop(Stack*,Item*);



int main(void){
	Node *head=initList();
	unsigned start_addr,node_num,reverse_len;
	scanf("%5u %u %u",&start_addr,&node_num,&reverse_len);

	Item tmp;
	for(int i=0;i<node_num;i++){
		scanf("%5u %u %d",&(tmp.addr),&(tmp.data),&(tmp.next));
		addNode(head,tmp);
	}
	
	int next_addr=start_addr;
	Node *app_order=initList();
	Node *tmp_node;
	while( next_addr != -1 ){
		if( tmp_node=findNode( head,next_addr ) ){
			next_addr=(tmp_node->item).next;
			addNode_(app_order,tmp_node);
		}else{printf("Error\n");}
	}
//printf("\noriginal order\n");
//	prtList(app_order,APP_ORDER);
//printf("\n\n");
	Stack *s=initStack();
	int i;
	for( i=0,tmp_node=app_order->next_app_order; 
			i<reverse_len ;i++,tmp_node=tmp_node->next_app_order ){
		push(s,tmp_node->item);
	} 
	_Bool firstLine=true;
	while( pop(s,&tmp) ){
		if( firstLine ){
			printf("%05u %d",tmp.addr,tmp.data);
			firstLine=false;
		}else{
			printf(" %05u\n%05u %d",tmp.addr,tmp.addr,tmp.data);
		}
	}
	while( tmp_node ){
		if ( firstLine ){
			printf("%05u %d",(tmp_node->item).addr,(tmp_node->item).data);
			firstLine=false;
		}else{
			printf(" %05u\n%05u %d",(tmp_node->item).addr,(tmp_node->item).addr,
									(tmp_node->item).data);
		}
		tmp_node=tmp_node->next_app_order;
	}
	printf(" -1");

	destroyList(app_order);
	destroyList(head);
	return 0;
}

Node *initList(){
	Node *ret=malloc(sizeof(Node));
	ret->next_org_order=ret->next_app_order=NULL;
	return ret;
}

void destroyList(Node *head){
	Node *tmp=head;
	Node *current=tmp->next_org_order;
	while(current){
		tmp=current->next_org_order;
		free(current);
		current=tmp;
	}
	free(head);
}

void addNode(Node* head,Item item){
	while( head->next_org_order )
		head=head->next_org_order;
	Node *new_node=malloc(sizeof(Node));
	new_node->item=item;
	new_node->next_org_order=NULL;
	new_node->next_app_order=NULL;
	head->next_org_order=new_node;
	return;
}

void prtList(Node *head,int order){
	if( ORG_ORDER == order ){
		while( head->next_org_order ){
			printf("%05u %u %05d\n", (head->next_org_order->item).addr,
				(head->next_org_order->item).data,(head->next_org_order->item).next);
			head=head->next_org_order;
		}
	}else if( APP_ORDER == order ){
		while( head->next_app_order ){
			printf("%05u %u %05d\n", (head->next_app_order->item).addr,
				(head->next_app_order->item).data,(head->next_app_order->item).next);
			head=head->next_app_order;
		}

	}else{}
	return;
}

Node * findNode(Node* head,unsigned addr){
	while( head->next_org_order ){
		if ( (head->next_org_order->item).addr == addr ){
			return head->next_org_order;
		}
		head=head->next_org_order;
	}
	return NULL;
}

void addNode_(Node* head,Node* new_node){
	while( head->next_app_order ){
		head=head->next_app_order;
	}
	head->next_app_order=new_node;
	return;
}

Stack * initStack(){
	Stack *ret=malloc(sizeof(Stack));
	ret->next=NULL;
	return ret;
}

void push(Stack* s,Item item){
	Stack* tmp=s->next;
	Stack* new=malloc(sizeof(Stack));
	new->item=item;
	new->next=tmp;
	s->next=new;
	return;
}

_Bool pop(Stack* s,Item *itemp){
	if( NULL == s->next )return false;
	*itemp=s->next->item;
	Stack* tmp=s->next->next;
	free(s->next);
	s->next=tmp;
	return true;
}
